package com.edu.leetcode.dataStruct;

import cn.hutool.db.handler.HandleHelper;

import java.util.*;

/**
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 *
 * @作者 five-five
 * @创建时间 2021/3/31
 */
public class Demo09 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,9,5,4,8,5,2,4,1};
        List<List<Integer>> lists = new Demo09().subsetsWithDup(nums);
        lists.forEach(System.out::println);

    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> resultSet = new HashSet<>();
        List<Integer> numsList = new ArrayList<>();
        for (int i : nums) {
            numsList.add(i);
        }
        dfs(resultSet, new ArrayList<>(), numsList, numsList.size());
        return new ArrayList<>(resultSet);
    }

    public void dfs(Set<List<Integer>> combinations, List<Integer> combination, List<Integer> nums, int size) {
        if (combination.size() > size) {
            return;
        }
        List<Integer> temp = new ArrayList<>(combination);
        combinations.add(temp);
        for (int i = 0; i < nums.size(); i++) {
            combination.add(nums.get(i));
            List<Integer> tempNums = new ArrayList<>(nums);
            int j = i;
            while (j >= 0) {
                tempNums.remove(0);
                j--;
            }
            dfs(combinations, combination, tempNums, size);
            combination.remove(combination.size() - 1);
        }
    }

}
